package interviewQuestions;

import java.io.IOException;
import java.util.Scanner;

/**
 * 分别按照二叉树的先序、中序和后序打印所有结点
 *
 * */

class TreeNode{
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
}

public class BinaryTreeTraversal {

    // 构建二叉树
    public TreeNode createBintree(TreeNode root) throws IOException {
        Scanner input = new Scanner(System.in);
        // 利用先序建立二叉树
        char value = (char) System.in.read();
        if(value == '#'){
            return null;
        }else{
            if(root == null){
                root = new TreeNode();
            }
            int val = value - '0';
            root.val = val;
            root.left = createBintree(root.left);
            root.right = createBintree(root.right);
        }
        return root;
    }

    // 先序遍历
    public void prev(TreeNode root){
        // 判断当前root是不是为空 为空就终止
        if(root == null){
            return;
        }
        // 先将root打印
        System.out.print(root.val + " ");
        // 再打印左孩子和右孩子
        prev(root.left);
        prev(root.right);
    }

    // 中序遍历
    public void mid(TreeNode root){
        // 判断当前root是不是为空 为空就终止
        if(root == null){
            return;
        }
        // 先打印左孩子
        mid(root.left);
        // 然后打印root
        System.out.print(root.val + " ");
        // 最后打印右孩子
        mid(root.right);
    }


    // 后序遍历
    public void after(TreeNode root){
        // 判断当前root是不是为空 为空就终止
        if(root == null){
            return;
        }
        // 先打印左孩子
        after(root.left);
        // 然后打印右孩子
        after(root.right);
        // 最后打印root
        System.out.print(root.val + " ");
    }

    public void threeOrders (TreeNode root) throws IOException {
        root = createBintree(root);

        prev(root);
        mid(root);
        after(root);
    }

    public static void main(String[] args) throws IOException {
        BinaryTreeTraversal b = new BinaryTreeTraversal();
        b.threeOrders(new TreeNode());
    }
}
